首页 > 试题广场 >

三角形最小路径和

[编程题]三角形最小路径和
  • 热度指数：7488 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。

数据范围：三角形数组行数满足 ，数组中的值都满足

例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时，对应的输出为11，
所选的路径如下图所示：

示例1

输入

[[10]]

输出

10
示例2

输入

[[2],[3,4],[6,5,7],[4,1,8,3]]

输出

11

说明

最小路径是 2 ， 3 ，5 ， 1
示例3

输入

[[1],[-1000,0]]

输出

-999
算法知识视频讲解
添加回答
Python 3
初心者托奇头像 初心者托奇
Python 
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        dp_lst = [0]
        for i in triangle:
            dp_lst2 = dp_lst.copy()
            dp_lst = [100000]
            for j in range(len(i)):
                dp_lst.append(min(dp_lst2[j: j + 3]) + i[j])
        return min(dp_lst[1:])
我只能说应该是最后两个用例出问题了，已经检查出-63结果应该是-69。

发表于 2022-08-18 23:53:31 回复(1)
Python 3
牛客878598322号头像 牛客878598322号
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        n=len(triangle)
        ans=[[0]*(i+1) for i in range(n)]
        ans[0][0]=triangle[0][0]
        for i in range(1,n):
            for j in range(i+1):
                if i==0 and j==0:
                    continue
                elif i==j:
                    ans[i][j]=ans[i-1][j-1]+triangle[i][j]
                elif j==0:
                    ans[i][j]=ans[i-1][j]+triangle[i][j]
                else:
                    ans[i][j]=triangle[i][j]+min(ans[i-1][j],ans[i-1][j-1])
        return min(ans[-1])
发表于 2022-04-26 19:33:21 回复(0)
Python 3
Joy_9头像 Joy_9 
#
class Solution:
    def minTrace(self , triangle: List[List[int]]) -> int:
        # write code here
        m=len(triangle)-1
        while m>0:
            for j in range(m):
                triangle[m-1][j]=min(triangle[m][j],triangle[m][j+1])+triangle[m-1][j]
            m-=1
        return triangle[0][0]

发表于 2022-01-23 07:49:20 回复(0)
提交观点

问题信息

动态规划 数组
难度：
3条回答 1974浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号